Predstavitev projekta
Naslov: Produktna struktura gostih grafov
Akronim projekta: BI-FR/26-27-PROTEUS-010
Vodja projekta: dr. Jochen Pascal Gollin
Vodilna institucija v Sloveniji: UP FAMNIT
Partnerska institucija: Université Clermont Auvergne
Financer projekta: Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije (ARIS)
Raziskovalno področje (ARIS): 1.01 - Matematika
Vrsta projekta: Znanstvenoraziskovalno sodelovanje med Slovenijo in Francijo
Trajanje projekta: 1. 1. 2026–31. 12. 2026
Opis projekta:
Avtorji Dujmović, Joret, Micek, Morin, Ueckerdt in Wood so v svojem temeljnem prispevku "Ravninski grafi imajo omejeno čakalno število" (“Planargraphs have bounded queue-number”) dokazali, da je vsak ravninski graf podgraf močnega krepkega produkta nekega grafa konstantne drevesneširine in neke poti.
Ta rezultat ima široko paleto aplikacij (o katerih bomo podrobneje razpravljali spodaj).
Nedavna prizadevanja Hlinenýja in Jedelskýja so omogočila razširitev te vrste teorije produktne strukture na goste grafe.
To dvostransko sodelovanje je osredotočeno na nadaljnji razvoj teorije produktne strukture za goste grafe, tako s strukturnega kot algoritmičnegavidika, kot tudi na iskanje aplikacij teorije za primerne probleme.
Izbira te teme je motivirana z več vidikov. Prvič, v zadnjih letih se je izkazalo, da je teorija strukture grafov močno in vsestransko orodje za reševanjeproblemov na številnih različnih področjih teorije grafov. Poleg tega obstaja veliko več prostora za nadaljnji razvoj bolj teoretičnih vidikov teorijestrukture grafov, zlasti v primeru gostih grafov.
Drugič, ta projekt je posebej usmerjen k prednostim posameznih raziskovalnih ekspertiz v obeh partnerskih državah, zlasti za izkoriščanje sinergijkomplementarnih prednosti vseh članov projekta.
Oddelek UP FAMNIT, v okviru katerega se izvaja projekt:
Oddelek za matematiko
Project presentation
Title: Product Structure of Dense Graphs
Project acronym: BI-FR/26-27-PROTEUS-010
Principal investigator: dr. Jochen Pascal Gollin
Leading institution in Slovenia: UP FAMNIT
Partner institution: Université Clermont Auvergne
Funding organization: Slovenian Research and Innovation Agency (ARIS)
Research field (ARIS): 1.01 - Mathematics
Duration: 1. 1. 2026–31. 12. 2026
Description:
In their seminal paper “Planar graphs have bounded queue-number” the authors (Dujmovic, Joret, Micek, Morin, Ueckerdt, and Wood) proved that anyplanar graph is a subgraph of a strong product of a graph of constant tree-width and a path.
This result has a wide range of applications (which we discuss more below).
Recent efforts by Hlinený and Jedelský enabled to overcome the problem of lifting this type of product structure theory to dense graphs.
This bilateral cooperation is focused on further developing product structure theory for dense graphs, both from a structural and algorithmic point ofview, as well as finding applications for the theory to suitable problems.
The choice of this topic is motivated by multiple aspects. Firstly, in recent years graph product structure theory has turned out to be a powerful andversatile tool for solving problems in many different areas of graph theory. Additionally, there is much more room to develop the more theoreticaspects of graph product structure theory further, especially in the dense case.
Secondly, this project is especially geared towards the strengths of the respective research terms in both partner countries, in particular to exploitthe synergies of complementary strengths of all members of the project.
